NOIP 2017 提高组初赛总结

应该是最后一次参加NOIP了吧,已经高二了时间和心思也不能安心得抽出来了。就认真总结一下这次的初赛卷吧。

初赛分析

试卷及答案资源

GitHub

说个笑话:试卷底部印着NOIP 2016 提高初赛

题目分析

有些题目我自己错了,而且只有答案,并不知道正解,所以打个*区分

单项选择

  1. 坑爹题目= = 日常摸奖(1/2)系列

    [NOI官网]的官网神奇公告 其实这道题原本在圈子里听说了,所以可以做出来的,但是日期就是这么迷迷糊糊地记错了

    2020年 NOI系列赛 不支持Pascal

    2022年 NOIP系列赛 不支持Pascal…

    结果错选了2020年。怎么说呢? 记得不准确 吧。

  2. 常识,没什么好说的

    直接丢一篇我当时复习时认为最好的文章 [CSDN]计算机原码、反码、补码详解

  3. 空间单位换算 $ 1600 * 900 * 16 / (8 * 1024) = 2812.5$

  4. *数学题 (听说今年初赛考的数学题特别多?)

    赛后分析:2016年10月1日是周六,2012年10月1日是星期一…然后发现 $ 365 \bmod{ 7 } = 1$ 。感觉不对劲?作了一张表

    日期星期真实星期考试时猜测
    2017.10.1
    2016.10.1
    2015.10.1
    2014.10.1
    2013.10.1
    2012.10.1
    2011.10.1
    1950.10.1
    1949.10.1
    1948.10.4

    这也差太远了吧!其实貌似推算星期也不只是隔4年变一天这么简单的

    一开始发现 [CSDN]计算任何一天是星期几的几种算法 有一个 Zeller公式 可以使用,但是估计是记不住。

    然后又找到了 [博客园]日历查询的算法 如何计算某一天是星期几 中详细的推导过程。

    最朴素的计算方法是计算 $ 中间间隔的总天数 \bmod 7$ 。中间要注意2000年是闰年,还可以把1949年12月31日和2017年12月31日作为2个原点。然后

    $ (2017-1949 = 68) * 365 + 17 = 24837 \bmod 7 = 1 $

    写了段程序暴力验证结果也是 24837

点击显/隐代码

然而还不是很确定这样解对不对,不过至少答案看起来是对的

  1. 图论+数学 基础题

    树的基本性质:总边数 = 结点数 - 1

    由此可以推得: $ m - k = n - 1 $ 解得 $ k = m - n + 1 $

  2. *求时间复杂度 与NOIP2013初赛15题相类似。

    正解都可以用 [网易博客]主项定理 Master Method 来求解,估计也是求时间复杂的的正解。我是还没怎么看懂,猜主要思想应该是把时间复杂度建立为一个 $ T(n) = a * T(n / b) + f(n) $ 的模型,然后比较 $ f(n) $ 与 $ n^{\log_b a} $ 两者的变化幅度(也就是数量级),取其中较大的那一个。

    这题解也不是很确定,猜可能带入特殊值是这样观察的:

    $ T(1) = 1 $

    $ T(2) = 2T(1) + 2 \log 2 = 2+2 \log 2 $

    $ T(3) = 2T(1) + 3 \log 3 = 2+3 \log 3 $

    $ T(4) = 2T(2) + 4 \log 4 = 4 + 4 \log 2 + 2 \log 2 $

    $ = 4 + 3(\log4) \approx n\log n $ ???

    $ T(5) = 2T(2) + 5 \log 5 = 4 + 4 \log 2 + 5 \log 5 $

    好吧, 复盘带入计算也不知道 怎么能得出C解。

    不过总结了下主项定理,应该是判断出 $ f(n) = n \log n =n^{\log_22} $ 即 数量级相当 ,然后得出时间复杂度在 $ f(n) $ 的基础上乘以 $ \log n $ 得出 $ O(n \log^2 n) $ 的。

  3. 常识,模拟栈操作

  4. *目测是图论+“极简单”的排列组合

    先明确一下定义:简单无向连通图

    连通:指任意2个点有路径相连[1]

    无向:任意一条连接u、v的边都表示u连v和v连u[1:1]

    简单图:不存在平行边和自环的图[2]

    所以说我的思路是找那些可以90°旋转4次而各不相同的种类数,再寻找只能180°旋转和不能旋转的种类数。但是貌似 漏了2条对角线加一条边 的这种情况,而且遗漏了其它能旋转的图形。 可能是 枚举的方法 不对(我是按加边枚举的,不知道有没有更好的方法)

  5. 隔板法!这玩意在考试之前还仔细研究过,是一个好东西。[百度百科]隔板法

    就是 $ C^{空隔数}_{要插入的隔板数} $ 在本题中则为 $ C^9_3 $ 再牢记 $ C^n_m = m! / (n!(m-n)!) $ 轻松解决

  6. *据说正解是递推公式求通项公式,(感觉用微积分可以做,然而没学),我是手工暴力到 $ 21/32 $ 或者多少分之64然后找规律做的。

  7. *估计应该是 题目意思弄错了 。题目给的2个数组是 有序数组 ,而 [百度]归并排序-复杂度 中所得出的时间复杂度应该是指数组无序的情况。有序的最坏情况可能是:

    设 $ n=5 $

    1-1;1-2;2-2;2-3;3-3;3-4;4-4;4-5;5-5

    共 $ 2n-1=9 $ 种这个意思,而不是无序数组的从头归并。

  8. 经典数学题

    A与B比较,若相等,则假币必在C,否则假币在A。最后统计n数量确认是否继续搜索

  9. 经典dp [Luogu]P1216 [USACO1.5]数字三角形 Number Triangles & IOI94 数字三角形

    印象特别深,因为据说是OI界第一道dp的题目。思路很简单,从左和从右路径中取一个较大路径继续走即可。 注意!此处由于所求的是路径上的数之和,与种数等无关,因此不可作死+1

  10. *数学 计算概率,至今不会计算

  11. 数学 水题 $ 1 / 20 * 360 = 18 $ 几何概型

不定项选择

  1. 对归并排序的还不是很熟悉,这张卷子又考了很多次归并,所以漏选了
  2. 栈模拟
  3. 这道题我备考时找到了这篇文章,挺不错的[cnblog]稳定排序和不稳定排序
  4. 常识
  5. 摸奖日常蹦(2/2) 王选奖貌似是CCF承办的一个奖项

问题求解

  1. 这道题在挑战程序设计竞赛上有类似的题型[3] ,貌似是用数学方法做的
  2. 暴力求解的,最小方案数漏了一种?

阅读程序写结果

  1. 暴力递归,把整棵树都画下来即可

  2. 看不出有什么规律

  3. 和拓扑排序有关的题目,应该是考你会不会拓扑的实现一类的

  4. 非常巧妙的几何题,从给定坐标出发不断以斜率为1或-1反弹,直到4角终止

完成程序

  1. 好吧,大整数除法一开始没看到题目中有%的操作,所以说做得非常迷茫,最后答案也没对几个。

  2. ​最长路径,感觉在哪里想过

个人总结

虽说是复盘,但是再看一遍还是好多题目不会。看来还是太水了。

感觉最后一个星期狂刷往届试卷非常非常有用。


20171020

成绩终于还是出来了,13.5+4.5+2+10+7=37。嗯,怎么说呢,果然还是太菜了呢,需要更加努力。


  1. https://baike.baidu.com/item/连通无向图 ↩︎ ↩︎

  2. https://baike.baidu.com/item/简单图 ↩︎

  3. P150 3.2.2 — 挑战程序设计竞赛 第二版·人民邮电出版社·【日】秋叶拓哉 岩田阳一 北川宜稔·ISBN 978-7-115-32010-0 ↩︎